\documentclass[utf8]{beamer}
\usepackage{import}
\usepackage{graphicx}
\usepackage{verbatim}
\usepackage[french]{babel}
\graphicspath{{img/}}

\usetheme{Darmstadt}

\title{Projet AMR}
\subtitle{Coloration de graphes}
\date{Janvier 2011}

\author{
Mohamed El-Fardi
\and
Lo\"ic Fournier
\and
Yann Hauquin
}
\institute{Universit\'e de Bordeaux I}
\setbeamercovered{transparent}
\begin{document}

\frame{\titlepage}


\begin{frame}
\frametitle{Algorithmes}
\begin{block}{Algorithme Glouton}
\begin{itemize}
\item \uncover<2->{Naïf}
\item \uncover<3->{Itératif}
\item \uncover<4->{Peu efficace}
\item \uncover<5->{Rapide}
\end{itemize}
\end{block}
\end{frame}

\begin{frame}
\frametitle{Complexité - Glouton}
\begin{itemize}
\item {Complexité : $O(n^{k})$}
\end{itemize}
\begin{block}{Pseudo-code}
\begin{tabbing}
Pour \= chaque \= sommet \= S du graphe G :\\
\> Pour chaque couleur C de la liste des couleurs :\\
\> \> Si aucun voisin de S n'est de couleur C\\
\> \> \> Couleur(S) = C\\
\> \> \> Break de la boucle\\
\> \> Fin Si\\
\> Si G n'est pas entièrement coloré\\
\> \> Couleur(S) = Nouvelle couleur\\
\> Fin Si\\
\> Fin Pour\\
Fin Pour\\
\end{tabbing}
\end{block}
\end{frame}

\begin{frame}
\frametitle{Algorithmes}
Probabilité = 0.15
\includegraphics[scale=0.32]{glouton.png}
\end{frame}

% ---------------------------

% ---------------------------

\begin{frame}
\frametitle{Algorithmes}
\begin{block}{Algorithme Backtrack}
\begin{itemize}
\item \uncover<2->{Récursif}
\item \uncover<3->{Relativement efficace}
\item \uncover<4->{Lent}
\item \uncover<5->{Complexité : $O(n^{k})}$
\end{itemize}
\end{block}
\end{frame}

\begin{frame}
\frametitle{Algorithmes}
Probabilité = 0.15
\includegraphics[scale=0.32]{backtrack.png}
\end{frame}

% ---------------------------

% ---------------------------

\begin{frame}
\frametitle{Algorithmes}
\begin{block}{Algorithme No-Choice}
\begin{itemize}
\item \uncover<2->{Itératif}
\item \uncover<3->{Moyennement efficace dans sa version non-optimisé}
\item \uncover<4->{Complexité : $O(\frac{m^{2}}{n^{2}})}$
\end{itemize}
\end{block}
\end{frame}

\begin{frame}
\frametitle{Algorithme No-Choice}
\begin{block}{Principales étapes}
\begin{itemize}
\item \uncover<2->{Recherche de la plus grande clique}
\item \uncover<3->{Coloration des sommets avec une couleur admissible}
\end{itemize}
\end{block}
\end{frame}


\begin{frame}
\frametitle{Algorithme No-Choice}
\begin{block}{Recherche de la plus grande clique}
\begin{itemize}
\item \uncover<2->{Calcul des degrés de chaque sommet}
\item \uncover<3->{Construction de la clique a l'aide de l'algorithme du cours}
\item \uncover<4->{Coloration de la plus grande clique}
\end{itemize}
\end{block}
\end{frame}

\begin{frame}
\frametitle{Algorithme No-Choice}
\begin{block}{Coloration des sommets avec une couleur admissible}
\begin{itemize}
\item \uncover<2->{Recherche des sommets non coloriés}
\item \uncover<3->{Calcul du nombre de couleurs admissible}
\item \uncover<4->{Coloration (ou pas) du sommet }
\end{itemize}
\end{block}
\end{frame}




\begin{frame}
\frametitle{Algorithmes}
Probabilité = 0.15
\includegraphics[scale=0.32]{nochoice.png}
\end{frame}

% ---------------------------

% ---------------------------

\begin{frame}
\frametitle{Algorithmes}
\begin{block}{Algorithme No-Choice optimisé}
On utilise exactement le même code que l'algorithme No-Choice avec une optimisation 
finale qui permet de colorier les sommets non encore coloriés par leur première
couleur admissible.
\end{block}
\end{frame}

\begin{frame}
\frametitle{Algorithmes}
Probabilité = 0.15
\includegraphics[scale=0.32]{nochoice2.png}
\end{frame}

% ---------------------------

% ---------------------------

\begin{frame}
\frametitle{Algorithmes}
\begin{block}{Réduction au problème SAT}

On exprime sous forme de formule logique la propriété d'un graphe d'être
k-coloriable.
~\\~\\
Pour tous les sommets i $\in$ V, on associe k variables : \\
$c_{i}^{k}\left\{\begin{tabular}{l}
1 si le sommet i est de couleur $c^{k}$ \\
0 sinon
\end{tabular}\right .$
~\\~\\~\\
Chaque sommet a au moins une couleur :\\
$\Phi_{1} = \bigwedge_{i \in V}{(c_{i}^{1} \lor c_{i}^{2} \lor \dots
  \lor c_{i}^{k})}$
~\\~\\
Chaque sommet comporte au plus une couleur:\\
$\Phi_{2} = \bigwedge_{i \in V}{\left[(\lnot c_{i}^{1} \lor \lnot
    c_{i}^2 \lor \dots \lor \lnot c_{i}^{k-1})$
~\\
$\land(\lnot c_{i}^{1} \lor
\lnot c_{i}^{2} \lor \dots \lor \lnot c_{i}^{k-2} \lor \lnot
c_{i}^{k})\land \dots \land(\lnot c_{i}^{2} \lor \lnot c_{i}^{3} \lor
\dots \lor \lnot c_{i}^{k})\right]}$

\end{block}
\end{frame}


\begin{frame}
\frametitle{Algorithmes}
\begin{block}{Réduction au problème SAT}

Deux voisins ne comportent pas la même couleur :\\
$\Phi_{3} = \bigwedge_{(i,j) \in E}{\left[\lnot (c_{i}^{1} \land c_{j}^{1})
    \land \lnot (c_{i}^{2} \land c_{j}^{2}) \land \dots \land
    \lnot (c_{i}^{k} \land c_{j}^{k})\right]}$
~\\~\\
Propriété d'un graphe k-coloriable :\\
$\Phi = \Phi_{1} \land \Phi_{2} \land \Phi_{3}$

\end{block}
\end{frame}


\begin{frame}
\frametitle{Algorithmes}
\begin{block}{Réduction au problème SAT}
\begin{itemize}
\item \uncover<2->{Génération d'un fichier CNF à partir des clauses}
\item \uncover<3->{Analyse du fichier CNF par minisat pour résolution}
\item \uncover<4->{Résultat $\in$ \{SATISFIABLE, UNSATISFIABLE, INDETERMINATE\}}
\item \uncover<5->{Si Résultat = SATISFIABLE, une k-coloration est possible}
\end{itemize}
\end{block}
\end{frame}

\begin{frame}
\begin{center}
\Huge{Une petite démonstration...}
\end{center}
\end{frame}

\end{document}
